class Node {
  constructor(key,h=0,left=NIL,right=NIL){
    this.key = key
    this.h = h
    this.left = left
    this.right = right
  }
}

function getNode(key) {
  return new Node(key,1);
}

const NIL = {
  key: undefined,
  left: null,
  right: null,
  height: 0
}

function update_height(root) {
  root.h = Math.max(root.left.h,root.right.h) + 1;
}

//获取前驱
function getPre(root) {
  let temp = root.left
  while(temp.right) temp = temp.right
  return temp
}

function left_rotate(root) {
  let newRoot = root.right;;
  root.right = newRoot.left;
  newRoot.left = root;

  update_height(root);
  update_height(newRoot);
  return newRoot;
}

function right_rotate(root) {

}

Node.prototype.insert = function(root, key) {
  if(!root) return getNode(key);
  if(key === root.key) return root;
  if(key < root.key) {
    root.left = this.insert(root.left,key);
  } else {
    root.right = this.insert(root.right,key);
  }

  update_height(root);
  return this.maintain(root);
}

Node.prototype.erase = function(root, key){
  if(!root) return root;
  if(key < root.key) {
    root.left = this.erase(root.left, key);
  } else if(key > root.key) {
    root.right = this.erase(root.right, key);
  } else {

    if(!root.left.key || !root.right.key){
      let temp = root.left ? root.left : root.right
    } else {
      let temp = getPre(root);
      root.key = temp.key;
      root.left = this.erase(root.left
      , temp.key);
    }
  }

  update_height(root);
  return this.maintain(root);
}

Node.prototype.maintain = function(root){
  if(Math.abs(root.left.h -root.right.h) < 2) return root;
  if(root.left.h > root.right.h) { //L
    if(root.left.right.h > root.left.left.h) { //LR
      root.left = left_rotate(root.left);
    }
  } else { //R
    if(root.right.left.h > root.right.right.h){ //RL
      root.right = right_rotate(root.right);
    }
  }
  root = 

  return root;
}